Automatic memory management, or garbage collection, is a mature field that has been studied for about fifty years. An extensive survey of the field is provided by the book ‘Garbage Collection: Algorithms for Dynamic Memory Management’ by R. Jones and R. Lins (Wiley, 1996), which is basic reading for anyone seriously involved in the art of garbage collection. Even since the publication of this book, the field has seen active development due to the significant commercial interest in Java and other virtual machine based programming environments and growing interest in intelligent systems.
U.S. patent application Ser. No. 12/147,419 by the same inventor, which is incorporated herein by reference in its entirety, presented a garbage collection system based on multiobjects. A multiobject is defined as a linearized tree of objects with one entry point and any number of exits.
The mentioned patent application provided that multiobject construction comprises copying the objects selected to form the multiobject into consecutive memory locations (with possibly some padding or holes, as described in the specification). The application also provided that the objects be stored in the linearized representation in a specific order, such as left-to-right depth first order, as described in the application.
The left-to-right depth first order is basically the order in which objects are visited when performing a depth-first traversal of the object graph and traversing the pointers within each object left-to-right, i.e., the pointer at the lowest memory address first; right-to-left depth first order is the same except that pointers within each object are traversed right-to-left, i.e., the pointer at the highest memory address first. Traversing the object graph is often called tracing in garbage collection literature.
In many programming environments, including the most popular virtual machines and runtimes for languages such as Java, C# and Lisp, dynamic updates to the object graph are possible (that is, data fields, or cells, containing pointers can be written at any time and made to point somewhere else or nowhere at all). Even without such updates, a new reference can be added in the nursery that points to the middle of an existing multiobject. The application noted that “in some embodiments a more liberal structure for multiobjects may be used than the strict linearized tree. For example, writes to within the multiobject may render parts of the multiobject unreachable, and added external references to objects within the multiobject may make it desirable to have nested multiobjects or entries pointing to within multiobjects.”
It is advantageous for a multiobject-based garbage collection system to maintain a reachability graph of multiobjects. As an application runs, it may perform arbitrary modification to the underlying object graph, implying corresponding changes to the multiobject graph. On the targeted large multiprocessor computers with very large memories, it can be expected that application programs will also utilize multiple threads of execution which are updating the object (and multiobject) graph concurrently. Locking, lock-free data structures and/or software transactional memory may be used for ensuring consistency of internal data structures during concurrent execution.
When a cell in an object is written by an application, the old value of that cell becomes unreachable unless it has references from other locations. Such updates may render parts of multiobjects unreachable (essentially the subtree referenced by the old value of the written cell).
Also, when a value is written to a cell or to a register, the value may point to the middle of a multiobject (it may be the root of a subtree of the multiobject). Many such values, particularly those written into registers, are short-lived, and there is no need to update the multiobject graph immediately.
Generally, it is not necessary to update the multiobject graph immediately when the object graph changes. However, multiobject garbage collection advantageously depends on the multiobject graph being up to date. Thus, it is desirable to bring the multiobject graph up to date at the beginning of each evacuation pause.
It is common practice in garbage collection and some other systems to use a software (or hardware) component called the write barrier to analyze writes and to record certain information about writes. Most garbage collection systems only require (the mutator part of) the write barrier to coarsely record which objects may have been written. Card marking is a popular implementation of a write barrier in such systems, leaving more work to be done in the card scanning phase (which is herein also considered part of the write barrier even though it may be done at garbage collection time). Write barrier implementations using hash tables and remembered sets have also been described in the literature. (Here, we interpret the term write barrier rather broadly, including not only the tests whether the write should be recorded (often inlined), but also the code that actually records the write, and the code that processes any write barrier buffers, remembered set buffers, or performs card scanning. Some other authors use it more narrowly, referring only to the test of whether a write should be recorded.)
In a multiobject garbage collection system, the multiobject graph is preferably updated at the start of each evacuation pause using the information saved by the write barrier.
One solution for efficiently maintaining a multiobject graph is to allow nested multiobjects, such that references to objects within a multiobject can be represented in the multiobject graph by a reference to a nested multiobject that has an implicit reference from its containing multiobject (the exact memory location containing the reference not necessarily known) and one or more references from other multiobjects or registers/roots.
It is also important to track how much space in each multiobject has been rendered inaccessible by writes to the multiobject. This information is required for accurately determining the priority of collecting each memory region (the priority sometimes called ‘gc_index’). Such determination in a multiobject garbage collection system requires determining the size or range of the subtree rendered inaccessible.
However, efficiently determining which memory addresses should be included in a nested multiobject and which memory addresses are rendered inaccessible by a write requires determining the range of a subtree in the multiobject as the multiobject was when it was originally created.
Linearization of trees (and arbitrary graph structures) is a well-known technique, and is widely deployed e.g. for storing trees in files, communicating them over data transmission networks, serialization, and implementing persistent object systems.
The write barrier in a garbage collector, including some copying write barriers, are described in Jones & Lins, e.g. pp. 150-153, 165-174, 187-193, 199-200, 214-215, 222-223 (and various details on other pages as well).
A use of linearized trees with attention to the end of a subtree was described in V. Gopalakrishna and C. E. Veni Madhavan: Performance Evaluation of Attribute-Based Tree Organization, ACM Transactions on Database Systems, 6(1):69-87, 1980. Among other things, they describe the creation of a linearized tree and a method for computing the end of a subtree from the address of the nearest right sibling. However, they do not describe updates to the tree once it has been created or accessing the original after such updates, and their method for computing the end of the subtree uses the address of the right sibling, which is presumed to be available at that point.
Another use of linearized trees, including left-to-right and right-to-left traversals and construction, including modifications to the tree by essentially reconstructing the entire tree and replacing subtrees, is described in J. Budgaard: The Development of an Ada Front End for Small Computers, ACM SIGAda Ada Letters, Vol. V, Issue 2, pp. 321-328, 1985. However, their system does not appear to include a means for finding the end of a subtree from a tree (other than performing a full traversal), their right-to-left traversals are for a different purpose (some compiler passes are easier to implement when traversing the intermediate tree representation in reverse order) and perform e.g. compiler optimization steps for each encountered node, not subtree last address determination.
J. E. Stucka and R. Wiss: Stack Algorithm for Extracting Subtree from Serialized Tree, IBM Technical Disclosure Bulletin, 37(3):3-6, 1994 presents “an efficient algorithm for tree processing in dynamic environments; it can be used to identify subtree members within a serialized tree or to construct an entire hierarchical tree from a serialized tree.” However, the method and its goals appear to be different from the method of the present invention.
Object versioning in general and multiversion concurrency control are well-known methods in database systems (see e.g. P. A. Bernstein, V. Hadzilacos and N. Goodman: Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987, Section 5, pp. 143-166). Also, logs have been used to record old values of modified locations in database systems at least since 1960's and later in the main memory context with software transactional memory. Software transactional memory is described e.g. in Nir Shavit & Dan Touitou: Software Transactional Memory, ACM Symposium on the Principles of Distributed Computing, 1995 (extended version) and M. Greenwald: Non-Blocking Synchronization and System Design, PhD Thesis, Department of Computer Science, Stanford University, 1999 (especially Section 3.2 pp. 40-65).
Lock-free hash tables are discussed e.g. in Hui Gao: Design and Verification of Lock-free Parallel Algorithms, PhD Thesis, Wiskunde en Natuurwetenschappen, Riksuniversiteit Groningen, 2005 (especially Section 2 pp. 21-56).
Unfortunately, no methods for efficiently determining the range of a subtree in the original version of a linearized tree modified by writes have been available. Even in the case of non-modified trees, the only known method is the one by Gopalakrishna & Madhavan, which requires storing the right sibling addresses, which consumes a significant amount of extra space and implies processing overhead when constructing the linearized tree.